package exercises.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode-cn.com/problems/fraction-to-recurring-decimal/">
 * 166. 分数到小数</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
 * <p>
 * 如果小数部分为循环小数，则将循环的部分括在括号内。
 * <p>
 * 如果存在多个答案，只需返回 任意一个 。
 * <p>
 * 对于所有给定的输入，保证 答案字符串的长度小于 104 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：numerator = 1, denominator = 2
 * 输出："0.5"
 * <p>
 * 示例 2：
 * <p>
 * 输入：numerator = 2, denominator = 1
 * 输出："2"
 * <p>
 * 示例 3：
 * <p>
 * 输入：numerator = 2, denominator = 3
 * 输出："0.(6)"
 * <p>
 * 示例 4：
 * <p>
 * 输入：numerator = 4, denominator = 333
 * 输出："0.(012)"
 * <p>
 * 示例 5：
 * <p>
 * 输入：numerator = 1, denominator = 5
 * 输出："0.2"
 *  
 * <p>
 * 提示：
 * <li>-231 <= numerator, denominator <= 231 - 1</li>
 * <li>denominator != 0</li>
 *
 * @author or2
 * @date 2021年10月03日 时间: 11:13
 */
public class No166 {
    public String fractionToDecimal(int numerator, int denominator) {
        /* 余数 */
        int remainder = numerator % denominator;
        /* 整数部分 */
        int integer = numerator / denominator;
        /* 可以帮助检测正负情况, 以及是否发生溢出 */
        int overflow = remainder * denominator;
        /* 无小数, 直接返回整数部分 */
        if (remainder == 0)
            if (/* 溢出 */ integer == Integer.MIN_VALUE && (numerator < 0 && denominator < 0))
                return String.valueOf(integer).substring(1);
            else
                return String.valueOf(integer);

        StringBuilder resBuilder = new StringBuilder();
        if (integer == 0 && overflow < 0 /* 出现溢出 */ && overflow != Integer.MIN_VALUE)
            resBuilder.append('-');
        resBuilder.append(integer);
        /* 若余数为负数, 将余数转正 */
        if (overflow < 0/* 出现溢出 */ && overflow != Integer.MIN_VALUE)
            remainder = -remainder;
        /* 计算余数部分 */
        resBuilder.append('.');
        /* -1 / Integer.MIN_VALUE 必须使用 LONG */
        long remainder2long = remainder;
        /* 使用`哈希表`记录是否出现循环小数 */
        Map<Long, Integer> loop = new HashMap<>();
        while (remainder2long != 0) {
            /* 记录小数所在答案位置 */
            loop.put(remainder2long, resBuilder.length());
            remainder2long *= 10;
            resBuilder.append(remainder2long / denominator);
            remainder2long %= denominator;

            /* 之前余数出现过, 替换为循环小数 */
            if (loop.containsKey(remainder2long)) {
                Integer index = loop.get(remainder2long);
                return String.format("%s(%s)", resBuilder.substring(0, index), resBuilder.substring(index));
            }
        }

        System.gc();
        try {
            Thread.sleep(12);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        return resBuilder.toString();
    }
}
